﻿#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
void swap(int* a, int n, int i)
{
	int tmp = a[n];
	a[n] = a[i];
	a[i] = tmp;
}

//向上调整算法
void AdjustUp(int* a, int child)
{
	while (child)
	{
		if (a[(child - 1) / 2] > a[child])
		{
			swap(a, (child - 1) / 2, child);
			child = (child - 1) / 2;
		}
		else
			break;
	}
}

//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 假设法，选出左右孩⼦中⼩的那个孩⼦
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			swap(a, child, parent);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void CreateNDate()
{
	// 造数据
	int n = 10000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (int i = 0; i < n; ++i)
	{
		int x = (rand() + i) % 1000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

void topk()
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");

	int* minheap = (int*)malloc(sizeof(int) * 10);//创造10个元素的小堆
	for (int i = 0; i < 10; i++)
	{
		fscanf(fout, "%d", &minheap[i]);
		AdjustUp(minheap, i);
	}
	
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		// 读取剩余数据，⽐堆顶的值⼤，就替换他进堆
		if (x > minheap[0])
		{
			minheap[0] = x;
			AdjustDown(minheap, 10, 0);
		}
	}

	for (int i = 0; i < 10; i++)
	{
		printf("%d ", minheap[i]);
	}
	fclose(fout);
}

int main()
{
	CreateNDate();
	topk();
	return 0;
}